package 面试题32_2_分行从上到下打印二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 13:19 2021/2/18
 * @Description：
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        if (root == null) {
            return new ArrayList<List<Integer>>();
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        int toBePrinted = 1;//当前层待打印的节点数
        int nextLevel = 0;//下一层的节点数量

        TreeNode currentNode;

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> levelList = new ArrayList<>();//存储每一层的内容

        while (!queue.isEmpty()) {
            currentNode = queue.poll();

            if (currentNode.left != null) {
                queue.add(currentNode.left);
                nextLevel++;
            }
            if (currentNode.right != null) {
                queue.add(currentNode.right);
                nextLevel++;
            }

            levelList.add(currentNode.val);
            toBePrinted--;
            if (toBePrinted == 0) {
                result.add(levelList);

                toBePrinted = nextLevel;
                //置空之前的内容
                levelList = new ArrayList<>();

                nextLevel = 0;
            }
        }

        return result;

    }
}
